package leetcode_800;

/**
 *@author 周杨
 *CountDifferentPalindromicSubsequences_730_ 计算一个字符串里不同的回文子序列
 *describe: 用动态规划 除了找转移方程还要考虑重复解空间的删除 AC 45%
 *see:https://blog.csdn.net/lili0710432/article/details/78659583
 *2018年10月14日 下午5:35:04
 */
public class CountDifferentPalindromicSubsequences_730_ {
	public int countPalindromicSubsequences(String S) {
		if(S.length()==0)
			return 0;
		final long MOD=1000000007;
		char chars[]=S.toCharArray();
		int dp[][]=new int[S.length()][S.length()];
		for(int j=0;j<S.length();++j) {
			dp[j][j]=1;
			for(int i=j-1;i>=0;--i) {//先从小区间遍历
				if(chars[i]==chars[j]) {
					dp[i][j]=2*dp[i+1][j-1];
					//开始找到最左和最右与chars[i]相等的值
					int left=i+1,right=j-1;
					while(left<=right&&chars[left]!=chars[i]) ++left;
					while(left<=right&&chars[right]!=chars[i]) --right;
					if(left==right)//只有一个
						dp[i][j]++;
					else if(left>right)//没有
						dp[i][j]+=2;
					else
						dp[i][j]-=dp[left+1][right-1];//越界了就给0
				}
				else {
					dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1];//减去重复区间的值
				}
				dp[i][j]=(int) ((dp[i][j]+MOD)%MOD);//防止越界
			}
		}
		return dp[0][S.length()-1];
    }
}
